#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* partition(struct ListNode* head, int target) {
    struct ListNode left_dummy, right_dummy;
    struct ListNode* left_tail = &left_dummy;
    struct ListNode* right_tail = &right_dummy;

    while (head != NULL) {
        if (head->val < target) {
            left_tail->next = head;
            left_tail = left_tail->next;
        } else {
            right_tail->next = head;
            right_tail = right_tail->next;
        }
        head = head->next;
    }

    left_tail->next = right_dummy.next;
    right_tail->next = NULL;

    return left_dummy.next;
}

void printList(struct ListNode* head) {
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
}

int main() {
    struct ListNode* node1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* node2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* node3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* node4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* node5 = (struct ListNode*)malloc(sizeof(struct ListNode));

    node1->val = 3;
    node2->val = 8;
    node3->val = 2;
    node4->val = 5;
    node5->val = 1;

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = NULL;

    int target = 5;
    struct ListNode* newList = partition(node1, target);
    printList(newList);

    return 0;
}